package com.hc.programming.string;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串
 * 示例 1：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * <p>
 * 示例 2：
 * 输入：s = "cbbd"
 * 输出："bb"
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/6/8 14:49
 */
public class 最长回文子串 {
    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome("bb"));
        System.out.println(longestPalindrome("aacabdkacaa"));
    }

    /**
     * 两边扩散法
     *
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        char[] chars = s.toCharArray();
        String result = null;
        for (int i = 0; i < chars.length; i++) {
            if (i == 0) {
                result = String.valueOf(chars[i]);
            }
            int offset = 0; // 偏移
            // 双字符相等，双字符往外扩散
            if (i + 1 < chars.length && chars[i] == chars[i + 1]) {
                if (result.length() < 2) {
                    result = s.substring(i, i + 2);
                }
                offset = 0;
                for (int j = 1; j <= i; j++) {
                    if (i + j + 1 >= chars.length || chars[i - j] != chars[i + j + 1]) {
                        break;
                    } else {
                        offset = j;
                    }
                }
                if (offset > 0 && offset * 2 + 2 > result.length()) {
                    result = s.substring(i - offset, i + offset + 2);
                }
            }
            // 单字符往外扩散
            if (i > 0) {
                offset = 0;
                for (int j = 1; j <= i; j++) {
                    if (i + j >= chars.length || chars[i - j] != chars[i + j]) {
                        break;
                    } else {
                        offset = j;
                    }
                }
                if (offset > 0 && offset * 2 + 1 > result.length()) {
                    result = s.substring(i - offset, i + offset + 1);
                }
            }
        }
        return result;
    }
}
